When a user of the World Wide Web requests a Web page, the user must wait until the page is available on his or her data processing system (e.g., computer, etc.) for viewing. In general, this wait occurs because the request for the Web page must traverse the Internet from the user's data processing system to the data processing system that is the source of the page, the request must be fulfilled, and the requested page must travel back to the user's system. If the Internet is congested or the data processing system that is the source of the page is overwhelmed with many concurrent requests for pages, the wait can be considerably long.
To shorten this wait, special data processing systems are deployed throughout the Internet that expedite the delivery of some Web pages. Some of these data processing systems expedite the delivery of Web pages by functioning as cache memories, which are also known as “caches.” For the purpose of this specification, a “cache” is defined as a cache memory. For example, a cache stores commonly requested Web pages and thereafter enables requests for those pages to be intercepted and fulfilled from the cache without retrieval form the principal memory. This expedites the delivery of the Web page in two ways. First, a cache eliminates the need for the request to travel all of the way to the system that is the ultimate source of the page, and, therefore, eliminates some the wait associated with with the transit. Second, a cache also reduces the number of Web page requests that must be fulfilled by the system that is the ultimate source of the page, and, therefore, the wait associated with contention for the system is eliminated.
FIG. 1 depicts a block diagram of a computer network in the prior art in which one of the network's nodes acts as a cache for another of the nodes. Computer network 100 comprises three nodes that are interconnected logically as shown. The salient characteristic of the topology of computer network 100 is that node 121 communicates with node 101 only through node 111, and, therefore, node 111 is capable of intercepting and fulfilling requests from node 121 for node 101. In other words, although there might be more than one physical telecommunication path between node 101 and node 111 (not shown in FIG. 1) and more than one physical telecommunication path between node 111 and node 121 (also not shown in FIG. 1), and even a direct physical telecommunication path between node 101 and 121, node 111 is logically in the path between node 101 and node 121.
From the perspective of node 121 and node 111, node 101 actually or apparently comprises a vast amount of information arranged in bundles, called “resources.” For the purposes of this specification, a “resource” is defined as an individually addressable bundle of information that can be requested by a node. For example, a resource might be an individual computer file (e.g., a World Wide Web page, a .gif file, a Java script, etc.) or a database record, etc. Although node 101 can actually comprise a vast amount of information if, for example, it is a disk farm, it can also apparently comprise the information if it acts as a gateway to a data network, such as the Internet.
When node 101 is bombarded with a large number of concurrent requests for resources from node 121, node 101 might not be able to instantaneously respond to all of the requests. Therefore, to reduce the average delay between when node 121 requests a resource from node 101 and when it receives the resource, node 111 functions as a cache for node 101.
FIG. 2 depicts a block diagram of the salient components of node 111 in accordance with the prior art. Node 111 comprises: processor 201, memory 202, receiver 210, transmitter 211, transmitter 213, and receiver 214. Processor 201 is either a general-purpose processor or a special-purpose processor that performs the functionality described herein with respect to FIG. 3. Memory 202 holds programs and data for processor 201 and comprises cache 203, which holds the cached resources for node 101. Node 111 uses receiver 210 for receiving data from node 121, transmitter 211 for transmitting to node 121, transmitter 213 for transmitting to node 101, and receiver 214 for receiving from node 121.
FIG. 3 depicts a flowchart of the operations performed by node 121 and node 111 when node 121 requests a resource from node 101 and node 111 intercepts the request, acts as a cache for node 101, and fulfills the request, if possible, or passes the request on to node 101, if necessary.
At step 301, node 111 stores one or more resources in cache 203, each of which resources is indexed by the resource identifier of the resource. For example, if the resource is a World Wide Web page (i.e., a hypertext markup language formatted file), the resource identifier might be the uniform resource locator or “URL” for the page (e.g., www.amazon.com/mccullers.htm, etc.). It is not germane to an understanding of the prior art or the present invention why some resources are stored in the cache data structure and why others are not.
At step 302, node 121 receives a resource identifier and a request for the resource. This request and resource identifier might, for example, originate with a user of node 121 as part of a World Wide Web browsing session (e.g., http://www.amazon.com/mccullers.htm, etc.).
At step 303, node 121 transmits: (i) the resource identifier, and (ii) a request for the resource to node 111, and at step 305 node 111 attempts to retrieve the requested resource from cache 203 using the resource identifier as the index into the cache data structure.
At step 306, node 111 determines if, in fact, the requested resource is in cache 203. If it is (i.e., a cache “hit”), then control passes to step 309; otherwise (i.e., a cache “miss”) control passes to step 307.
If control passes to step 307, it means that the requested resource is not in cache 203 in node 111, that node 111 cannot fulfill the request itself, and, therefore, that node 111 must request the resource from node 101. Therefore, at step 307, node 111 transmits the resource identifier and request for the resource identifier to node 101, and at step 308 node 111 receives the requested resource. When the requested resources is in cache 203, and, therefore, that steps 307 and 308 can be avoided, the wait that a user must tolerate between when he or she requests a Web page and when the Web page is provided is usually reduced.
At step 309, node 111 transmits the resource to node 121, as requested, whether the requested resource was in cache 203 or not.
The increasing size and complexity of the Internet, and its increasing use for transmitting multimedia resources has created the need for improved caching techniques.